package com.hqq.leetcode.dp;

/**
 * BackPack 背包问题
 * Description:
 * Given n items with size Ai, an integer m denotes the size of a backpack.
 * How full you can fill this backpack?
 * Input:
 * [2,3,5,7],11
 * [2,3,5,7],12
 * Output
 * 10
 * 12
 * <p>
 * Idea:
 * 递推公式 dp[i][j] = Math.max(dp[i-1][j-A[i]]+A[i],d[i-1][j])
 * Created by heqianqian on 2017/9/15.
 */
public class BackPack {

    public static void main(String[] args) {
        int[] A = new int[]{2, 3, 5, 7};
        BackPack bp = new BackPack();
        int max = bp.backPack(11, A);
        System.out.println(max);
        max = bp.backPack(12, A);
        System.out.println(max);
    }

    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @return The maximum size
     */
    public int backPack(int m, int[] A) {
        // write your code here
        int[] dp = new int[m + 1];
        for (int i = 0; i < A.length; i++) {
            for (int j = m; j > 0; j--) {
                if (j >= A[i]) {//如果背包容量大于当前物品的容量
                    dp[j] = Math.max(dp[j], dp[j - A[i]] + A[i]);
                }
            }
        }
        return dp[m];
    }

    public int backPack1(int m, int[] A) {
        int[][] dp = new int[A.length][m + 1];//dp[i][j]用来表示当可选i个物品时且背包的容量为j时能装入的最大空间 之所以是m+1因为数组下标是从0开始算的
        for (int i = 0; i < A.length; i++) {
            dp[i][0] = 0;//当背包最大容量是0时 无论可选多少个商品最大可放入的大小都是0
        }
        for (int j = 1; j < m + 1; j++) {
            /*先考虑只能放入第0个物品的情况*/
            if (A[0] <= j) {//如果第0个物品的大小小于等于当前背包的大小 那么可以放入背包的最大大小就是第0个物品的大小
                dp[0][j] = A[0];
            } else {//否则可以放入的最大大小就是0
                dp[0][j] = 0;
            }
            for (int i = 1; i < A.length; i++) {
                //如果当前物品的大小大于背包的大小 那么当前商品无法放入 能放入的最大空间就是之前可以放入的最大空间
                if (A[i] > j) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j - A[i]] + A[i], dp[i - 1][j]);
                }
            }
        }
        return dp[A.length - 1][m];
    }
}
